We consider the problem of allocating applicants to courses, where each applicant\udhas a subset of acceptable courses that she ranks in strict order of preference. Each\udapplicant and course has a capacity, indicating the maximum number of courses and\udapplicants they can be assigned to, respectively. We thus essentially have a many-tomany\udbipartite matching problem with one-sided preferences, which has applications\udto the assignment of students to optional courses at a university.\udWe consider additive preferences and lexicographic preferences as two means of extending\udpreferences over individual courses to preferences over bundles of courses.\udWe additionally focus on the case that courses have prerequisite constraints: we will\udmainly treat these constraints as compulsory, but we also allow alternative prerequisites.\udWe further study the case where courses may be corequisites.\udFor these extensions to the basic problem, we present the following algorithmic results,\udwhich are mainly concerned with the computation of Pareto optimal matchings\ud(POMs). Firstly, we consider compulsory prerequisites. For additive preferences, we\udshow that the problem of finding a POM is NP-hard. On the other hand, in the\udcase of lexicographic preferences we give a polynomial-time algorithm for finding a\udPOM, based on the well-known sequential mechanism. However we show that the\udproblem of deciding whether a given matching is Pareto optimal is co-NP-complete.\udWe further prove that finding a maximum cardinality (Pareto optimal) matching is\udNP-hard. Under alternative prerequisites, we show that finding a POM is NP-hard\udfor either additive or lexicographic preferences. Finally we consider corequisites. We\udprove that, as in the case of compulsory prerequisites, finding a POM is NP-hard\udfor additive preferences, though solvable in polynomial time for lexicographic preferences.\udIn the latter case, the problem of finding a maximum cardinality POM is\udNP-hard and very difficult to approximate.
展开▼
